#include <iostream>
#include <fstream>
using namespace std;

template<typename Object>
class BinarySearchTree
{
private:
    class BinaryNode
    {
    public:
        Object data;
        BinaryNode* parent;
        BinaryNode* left;
        BinaryNode* right;
        BinaryNode(){
            data=0;
            parent=nullptr;
            left=nullptr;
            right=nullptr;
        }
        BinaryNode(const Object& A,const BinaryNode*& B,const BinaryNode*& C,const BinaryNode*& D): 
             data(A),parent(B),left(C),right(D) {}
    };
    BinaryNode* root=nullptr;
    void print(BinaryNode* t){
        if(t->left) print(t->left);
        cout<<setw(8)<<setiosflags(ios::left)<<(t->data);
        if(t->right) print(t->right);
    }
    void vectorprint(vector<Object> &A,BinaryNode* t){
        if(t->left) vectorprint(A,t->left);
        A.push_back(t->data);
        if(t->right) vectorprint(A,t->right);
    }
    BinaryNode* findMax(BinaryNode* t) const{
        if(t->right) return findMax(t->right);
        else return t;
    }
    BinaryNode* findMin(BinaryNode* t) const{
        if(t->left) return findMin(t->left);
        else return t;
    }
    bool isEmpty(){
        if(root) return 1;
        else return 0;
    }
    bool contains(const Object& x,BinaryNode* t)const{
        if(t==nullptr) return 0;
        else if(t->data==x) return 1;
        else if(t->data>x) return contains(x,t->left);
        else if(t->data<x) return contains(x,t->right);
    }
    void remove(const Object& x,BinaryNode* t){
        if(t==nullptr) return;
        else if(t->data==x){
            if(t->left&&t->right){
                BinaryNode* p=findMin(t->right);
                p->parent->left=nullptr;
                if(t->parent){
                    if(t->data<t->parent->data) t->parent->left=p;
                    else t->parent->right=p; 
                }
                else root=p;
                p->left=t->left;
                p->right=t->right;
                p->parent=t->parent;
            }
            else if(t->left){
                if(t->parent){
                    if(t->data<t->parent->data) t->parent->left=t->left;
                    else t->parent->right=t->left;
                }
                else root=t->left;
            }
            else if(t->right){
                if(t->parent){
                    if(t->data<t->parent->data) t->parent->left=t->right;
                    else t->parent->right=t->right;
                }
                else root=t->right;
            }
            else if(t->parent){
                if(t->data<t->parent->data) t->parent->left=nullptr;
                else t->parent->right=nullptr;
                }
            else root=nullptr;
            delete t;
        }
        else if(t->data>x) remove(x,t->left);
        else if(t->data<x) remove(x,t->right);
    }
    void makeEmpty(BinaryNode* &t){
        if(t!=nullptr){
            makeEmpty(t->left);
            makeEmpty(t->right);
        }
        t=nullptr;
    }
    BinaryNode* clone(BinaryNode* t)const{
        if(t==nullptr) return nullptr;
        else return new BinaryNode{t->data,t->parent,clone(t->left),clone(t->right)};
    }
public:
    void insert(const Object &x){
        BinaryNode *now=root;
        BinaryNode *last=nullptr;
        bool isleft=1;
        while(now!=nullptr){
            last=now;
            if(x<now->data){
                now=now->left;
                isleft=1;
            }
            else{
                now=now->right;
                isleft=0;
            }
        }
        BinaryNode *leaf=new BinaryNode;
        leaf->parent=last;
        leaf->data=x;
        leaf->left=nullptr;
        leaf->right=nullptr;
        if(last){
            if(isleft){
                last->left=leaf;
            }
            else last->right=leaf;
        }
        else root=leaf;
    }
    void print(){
        if(root) print(root);
        cout<<endl;
    }
    void vectorprint(vector<Object> &A){
        A.clear();
        if(root) vectorprint(A,root);
    }
    const Object& findMax() const{
        return findMax(root)->data;
    }
    const Object& findMin() const{
        return findMin(root)->data;
    }
    bool contains(const Object& x)const{
        return contains(x,root);
    }
    void remove(const Object& x){
        remove(x,root);
    }
    BinarySearchTree(){
        root=nullptr;
    }
    BinarySearchTree(const BinarySearchTree& rhs){
        root=clone(rhs.root);
    }
    ~BinarySearchTree(){
        makeEmpty(root);
    }
};